package cn.edu.nju.ws.sview.reasoning;

import java.io.IOException;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Properties;

import cn.edu.nju.ws.sview.crawler.Crawler;
import cn.edu.nju.ws.sview.crawler.Element;
import cn.edu.nju.ws.sview.database.DBOperations;
import cn.edu.nju.ws.sview.rdf.Resource;
import cn.edu.nju.ws.sview.rdf.ResourceFactory;
import cn.edu.nju.ws.sview.rdf.SupmagicResource;
import cn.edu.nju.ws.sview.rdf.TemporaryRDFResource;
import cn.edu.nju.ws.sview.rdf.URIResource;
import cn.edu.nju.ws.sview.reasoning.magicsets.MagicTemplates;
import cn.edu.nju.ws.sview.reasoning.provenance.FromRDFDocument;
import cn.edu.nju.ws.sview.reasoning.provenance.FromReasoning;
import cn.edu.nju.ws.sview.reasoning.provenance.Provenance;
import cn.edu.nju.ws.sview.reasoning.provenance.ProvenanceFactory;
import cn.edu.nju.ws.sview.reasoning.reasoner.ViewReasoner;
import cn.edu.nju.ws.sview.views.View;

/**
 * @author Gong Saisai
 *封装了所有推理引擎上的相关方法
 * 
 */
public class KnowledgeBase {
	/**
	 * 当查询结果数目超过TERMINATE_NUM，推理结束，以防递归程序爆炸
	 */
	public final static int TERMINATE_NUM;
	/**
	 * 当查询时间超过TERMINATE_TIME时，推理结束，以防递归程序由于
	 * 内在的遍历路径问题造成内存消耗过大
	 */
	public final static long TERMINATE_TIME;
	
	static{
	   	 Properties properties = new Properties();
	   	 try {
				properties.load(View.class.getClassLoader().getResourceAsStream("conf.properties")) ;
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			TERMINATE_NUM = Integer.parseInt(properties.getProperty("reasoning_terminate_num"));
			TERMINATE_TIME = Long.valueOf(properties.getProperty("reasoning_terminate_time"));
			properties.clear();
			properties = null;
	}
	
    private WorkingMemory facts;
	private ProductionMemory rules;
	
	private ViewReasoner viewResoner = null;
	
	/*used for datamember value computation
	 * to judge whether this turn of reasoning is finished
	 * */
	private boolean isFinished = true;
	
	public KnowledgeBase(WorkingMemory facts, ProductionMemory rules) {
		this.facts = facts;
		this.rules = rules;
		if (this.facts == null) {
			this.facts = new WorkingMemory();
		}
		if (this.rules == null) {
			this.rules = new ProductionMemory();
		}
	}
	
	public KnowledgeBase() {
		this.facts = new WorkingMemory();
		this.rules = new ProductionMemory();
	}
	
	public void setViewReasoner(ViewReasoner viewReasoner){
		this.viewResoner = viewReasoner;
	}
	
	/*used for datamember value computation 
	 * to judge whether this turn of reasoning is finished
	 * This value is set in the reasoning process
	 * */
	public boolean isFinished(){
		return this.isFinished;
	}
	
	public void addFact(GroundAtom fact){
		this.facts.add(fact) ;
	}
	
	public void addRule(Rule rule){
		this.rules.addRule(rule) ;
	}
	
	/**
	 * 如果当前Atom参数绑定情况没有向数据管理处请求过，那么首先从外存working memory导入facts到内存，<br>
	 * 然后向内存working memory进行查询
	 * ad hoc的优化：如果查询的参数都绑定，那么先检查内存中是否有相应事实，如果已经存在，那么无需请求。
	 * 
	 * 在推理过程中判断是否相关数据下载结束了，如果有一个文档数据未准备好，那么isFinished
	 * 值为false，并且该值保持不变了
	 * 
	 * @param queryPattern.当前Atom绑定情况
	 * @param equalTerms.当前Atom限定哪些参数相同
	 * @param prevdelta.用于semi naive
	 * @param flag. 表明是否使用上一轮推出的事实
	 * @param loadFromKB.是否从知识库加载事实
	 * @return 与查询相关的结果集合
	 * @throws SQLException 
	 * 
	 */
    private HashSet<GroundAtom> getFacts(Predicate pred,QueryArg key,ArrayList<ArrayList<Integer>> equalTerms, HashMap<Predicate,HashSet<GroundAtom>> prevdelta,boolean flag,boolean loadFromKB) throws SQLException{
    	HashSet<GroundAtom> result = null;

		if (loadFromKB) {
			boolean ff = true;
			Resource resource = pred.getResource();
			if (!(resource instanceof URIResource))
				ff = false;
			else if (((URIResource) resource).getURI().startsWith(
					ResourceFactory.INTERNAL_URI_PREFIX)) {
				ff = false;
			}

			if (ff) {
				int QueryBoundArgs = 0;
				if (key != null) {
					if (key instanceof BothArg)
						QueryBoundArgs = 2;
					else
						QueryBoundArgs = 1;
				}

				// ad hoc的优化：如果查询的参数都绑定，那么先检查内存中是否有相应事实，如果已经存在，那么无需请求。
				if (QueryBoundArgs != pred.getArity()
						|| (result = this.facts.getTupleForQuery(pred, key,
								equalTerms, prevdelta, flag)).size() == 0) {
					ArrayList<Term> terms = new ArrayList<Term>();
					Constant firstArg = null;
					Constant secondArg = null;
					if (key != null) {
						if (key instanceof FirstArg) {
							firstArg = ((FirstArg) key).getFirstArg();
						} else if (key instanceof SecondArg) {
							secondArg = ((SecondArg) key).getSecondArg();
						} else {
							BothArg bothArg = (BothArg) key;
							firstArg = bothArg.getFirstArg();
							secondArg = bothArg.getSecondArg();
						}
					}

					ArrayList<Constant> constants = new ArrayList<Constant>();
					if (firstArg != null)
						constants.add(firstArg);
					if (secondArg != null)
						constants.add(secondArg);

					for (int i = 0; i < pred.getArity(); i++) {
						if (i == 0 && firstArg != null) {
							terms.add(firstArg);
						} else if (i == 1 && secondArg != null) {
							terms.add(secondArg);
						} else
							terms.add(new Variable("x" + i));
					}
					Atom<Term> queryAtom = new Atom<Term>(pred, terms);

					/* Load facts from KB firstly */
					HashSet<GroundAtom> facts = Repository.getInstance()
							.getGroundAtomsByAtom(queryAtom);

					/* check whether the constant resource are valid neighors */
					if (firstArg != null
							&& firstArg.getResource() instanceof URIResource) {
						URIResource uriResource = (URIResource) firstArg
								.getResource();
						if (this.viewResoner!=null&&this.viewResoner.getEntities()
								.contains(uriResource)) {
							for (GroundAtom atom : facts) {
								ArrayList<Constant> m = atom.getTerms();
								boolean f = false;
								for (int i = 1; i < m.size(); i++) {
									Resource res = m.get(i).getResource();
									if (res instanceof URIResource) {
										URIResource uResource = (URIResource) res;
										int uriID = uResource.getID();
										this.viewResoner
												.storeNeighbors(uResource);
										String status = DBOperations.getValidStatus(uriID) ;
										if(!status.equals(URIResource.VALID)&&
												Crawler.getInstance().checkStatus(uResource)==Crawler.STATUS_UNSUBMITTED){
											if(this.isFinished){
												this.isFinished = false;
											}
											Crawler.getInstance().submitURI(uResource) ; 
											Crawler.getInstance().promoteWeight(uResource, Element.LEVEL_1);
										}
										
									} else {
										f = true;
										break;
									}
								}
								/* The value is not uri resource */
								if (f)
									break;
							}
						}
					}
					if (secondArg != null
							&& secondArg.getResource() instanceof URIResource) {
						URIResource uriResource = (URIResource) secondArg
								.getResource();
						if (this.viewResoner!=null&&this.viewResoner.getEntities()
								.contains(uriResource)) {
							for (GroundAtom atom : facts) {
								ArrayList<Constant> m = atom.getTerms();
								boolean f = false;
								for (int i = 0; i < m.size() - 1; i++) {
									Resource res = m.get(i).getResource();
									if (res instanceof URIResource) {
										URIResource uResource = (URIResource) res;
										int uriID = uResource.getID();
										this.viewResoner
												.storeNeighbors(uResource);
										String status = DBOperations.getValidStatus(uriID) ;
										if(!status.equals(URIResource.VALID)&&
												Crawler.getInstance().checkStatus(uResource)==Crawler.STATUS_UNSUBMITTED){
											if(this.isFinished){
												this.isFinished = false;
											}
											Crawler.getInstance().submitURI(uResource) ; 
											Crawler.getInstance().promoteWeight(uResource, Element.LEVEL_1);
										}
									} else {
										f = true;
										break;
									}
								}
								/* The value is not uri resource */
								if (f)
									break;
							}
						}
					}

					this.facts.addAll(facts);
					result = this.facts.getTupleForQuery(pred, key, equalTerms,
							prevdelta, flag);
				}
			}
		}

		result = this.facts.getTupleForQuery(pred, key, equalTerms, prevdelta,
				flag);
		return result;
    }
    
    /**
     * 进行查询计算，返回结果，包含了要显示的列和不要显示的列。
     * @param query 查询
     * @param loadFromKB. 判断需从知识库中提取事实（有些情况下可以使用addFact加入需要的事实，不再从知识库提取）
     * @param srcDocs.推理用到的相关数据源
     * @return
     * @throws SQLException 
     */
	public HashSet<GroundAtom> Evaluate(Atom<Term> query,boolean loadFromKB,HashSet<String> srcDocs) throws SQLException{
		HashSet<GroundAtom> relation = EvaluateWithMagicSetsOptimisation(srcDocs,query,loadFromKB,false);
		return relation;
    } 
	
    /**
     * 进行查询计算，返回结果，包含了要显示的列和不要显示的列。
     * @param query 查询
     * @param loadFromKB. 判断需从知识库中提取事实（有些情况下可以使用addFact加入需要的事实，不再从知识库提取）
     * @return
     * @throws SQLException 
     */
	public HashSet<GroundAtom> Evaluate(Atom<Term> query,boolean loadFromKB) throws SQLException{
		HashSet<String> srcDocs = new HashSet<String>();
		HashSet<GroundAtom> relation = EvaluateWithMagicSetsOptimisation(srcDocs,query,loadFromKB,false);
		return relation;
    } 
	
    /**
     * 进行查询计算，返回结果，包含了要显示的列和不要显示的列。
     * @param srcDocs.推理用到的相关数据源
     * @param query 查询
     * @param loadFromKB. 判断需从知识库中提取事实（有些情况下可以使用addFact加入需要的事实，不再从知识库提取）
     * @param existTest. 判断是否有值就结束推理
     * @return
     * @throws SQLException 
     */
	public HashSet<GroundAtom> Evaluate(HashSet<String> srcDocs,Atom<Term> query,boolean loadFromKB,boolean existStop) throws SQLException{
		HashSet<GroundAtom> relation = EvaluateWithMagicSetsOptimisation(srcDocs,query,loadFromKB,existStop);
		return relation;
    } 
	
    /**
     * 进行查询计算，返回结果，包含了要显示的列和不要显示的列。
     * @param query 查询
     * @param loadFromKB. 判断需从知识库中提取事实（有些情况下可以使用addFact加入需要的事实，不再从知识库提取）
     * @param existTest. 判断是否有值就结束推理
     * @return
     * @throws SQLException 
     */
	public HashSet<GroundAtom> Evaluate(Atom<Term> query,boolean loadFromKB,boolean existStop) throws SQLException{
		HashSet<String> srcDocs = new HashSet<String>();
		HashSet<GroundAtom> relation = EvaluateWithMagicSetsOptimisation(srcDocs,query,loadFromKB,existStop);
		return relation;
    } 
	
	/**
	 * Seminaive evaluation结合了magic sets optimization
	 * @param srcDocs.推理用到的相关数据源
	 * @param query
	 * @param loadFromKB
	 * @param existStop. 标识有值就结束推理
	 * @throws SQLException 
	 * @return.查询结果可以为空但不为NULL
	 */
	private HashSet<GroundAtom> EvaluateWithMagicSetsOptimisation(HashSet<String> srcDocs,Atom<Term> query,boolean loadFromKB,boolean existStop) throws SQLException{
		ArrayList<Rule> oldruleList = this.rules.getRelevantRules(query) ;
		return this.EvaluateWithMagicSetsOptimisationWithRules(srcDocs,query, oldruleList,loadFromKB,existStop) ;
	}
	
	/**
	 * Seminaive evaluation结合了magic sets optimization
	 * @param srcDoc.推理用到的相关数据源
	 * @param query
	 * @param oldruleList
	 * @param loadFromKB 
	 * @param existStop
	 * @throws SQLException 
	 * @return.查询结果可以为空但不为NULL
	 */
	private HashSet<GroundAtom> EvaluateWithMagicSetsOptimisationWithRules(HashSet<String> srcDocs,Atom<Term> query,ArrayList<Rule> oldruleList,boolean loadFromKB,boolean existStop) throws SQLException{
		MagicTemplates mt = new MagicTemplates(query,oldruleList);
		mt.rewriting();
		ArrayList<GroundAtom> FactSet = mt.getSeed();
		for(GroundAtom seedFact:FactSet){
			this.facts.add(seedFact) ;
		}
		ArrayList<Rule> ruleList = mt.getRewrittenRules();
		for(Rule r:ruleList){
			this.rules.addRule(r) ;
		}
		HashSet<GroundAtom> relation = SemiNaiveEvaluateWithRules(srcDocs,query,ruleList,loadFromKB,existStop);
		return relation;
	}
	
	/**
	 * Seminaive Evaluation of the query
	 * @param srcDocs. 推理用到的相关数据源
	 * @param query.查询
	 * @param ruleList.回答查询相关的规则集合
	 * @param loadFromKB.是否需要从KB加载事实
	 * @param existStop. 标识有值就结束推理
	 * @throws SQLException 
	 * @return.返回结果可以为空但不为NULL
	 */
    private HashSet<GroundAtom> SemiNaiveEvaluateWithRules(HashSet<String> srcDocs,Atom<Term> query,ArrayList<Rule> ruleList,boolean loadFromKB,boolean existStop) throws SQLException{
    	HashMap<Predicate, HashSet<GroundAtom>> delta = new HashMap<Predicate, HashSet<GroundAtom>>();
    	for (int i = 0; i < ruleList.size(); i++) {
			Rule r = ruleList.get(i);
			Predicate pred = r.getHead().getPredicate();
			HashSet<GroundAtom> relation = Instantiate(r, null,-1,loadFromKB);
			if (relation != null) {
				////判断查询是否有值
				if(existStop && pred.equals(query.getPredicate())){
					Predicate qpred = query.getPredicate();
					Pattern pattern = query.getPattern();
					QueryArg  key = this.makeQueryArg(qpred, pattern) ;
					HashSet<GroundAtom> queryResult = this.getFacts(qpred,key, pattern
							.getEqualTerms(), null,false,loadFromKB);
					if(queryResult.size()>0){
						return queryResult;
					}
				}
				
				HashSet<GroundAtom> mRelation = this
				.removeDeducedTuples(pred, relation);
	        	if (mRelation.size() > 0) {
			         this.facts.addAll(mRelation);
			         this.updateDelta(delta, pred, mRelation);
         		}
			}
		}
    	
		if (delta.size() != 0) {
			long startTime = System.currentTimeMillis();
			boolean newFact = true;
			stop:while (newFact) {
				newFact = false;
				HashMap<Predicate, HashSet<GroundAtom>> prevdelta = delta;
				delta = new HashMap<Predicate, HashSet<GroundAtom>>();
				for (int i = 0; i < ruleList.size(); i++) {
					Rule r = ruleList.get(i);
					Predicate pred = r.getHead().getPredicate();
					HashSet<GroundAtom> relation = null;
					
					try{
						relation = SemiInstantiate(r,prevdelta,loadFromKB);
					}catch (OutOfMemoryError e) {
						// TODO: handle exception
						break stop;
					}
					
					if (relation != null) {
						////判断查询是否有值
						if(existStop && pred.equals(query.getPredicate())){
							Predicate qpred = query.getPredicate();
							Pattern pattern = query.getPattern();
							QueryArg  key = this.makeQueryArg(qpred, pattern) ;
							HashSet<GroundAtom> queryResult = this.getFacts(qpred,key, pattern
									.getEqualTerms(), null,false,loadFromKB);
							if(queryResult.size()>0){
								return queryResult;
							}
						}
						HashSet<GroundAtom> mRelation = this
								.removeDeducedTuples(pred, relation);
						if (mRelation.size() > 0) {
							this.facts.addAll(mRelation);
							this.updateDelta(delta, pred, mRelation);
							newFact = true;
							
							//test if terminate by reasoning num
							if(pred.equals(query.getPredicate())){
								if(isTerminate(query, loadFromKB)){
									break stop;
								}
							}
						}
					}
					
					//test if terminate by reasoning time
					if(System.currentTimeMillis()-startTime>=KnowledgeBase.TERMINATE_TIME){
						break stop;
					}
				}
			}
		}
		//modify trace
		Predicate pred = query.getPredicate();
		Pattern pattern = query.getPattern();
		QueryArg  key = this.makeQueryArg(pred, pattern) ;
		HashSet<GroundAtom> queryResult = this.getFacts(pred,key, pattern
				.getEqualTerms(), null,false,loadFromKB);
		HashSet<String> docs = this.removeEdgesfromTrace(queryResult) ;
		srcDocs.addAll(docs);
		return queryResult;
    }
    
    /**
     * Seminaive instantiations of the rule. For every predicate which has new facts according to prevdelta, restrict its instances and do evaluation.Combine the results.
     * @param r.The rule to be evaluated
     * @param prevdelta. The map contains all the predicate having new facts in the last run of evaluation
     * @param loadFromKB. Whether load facts from KB
     * @return the relation  not null
     * @throws SQLException 
     */
    private HashSet<GroundAtom> SemiInstantiate(Rule r,HashMap<Predicate,HashSet<GroundAtom>> prevdelta,boolean loadFromKB) throws SQLException, OutOfMemoryError{
    	HashSet<GroundAtom> unionRel = new HashSet<GroundAtom>();
		ArrayList<Atom<Term>> literals = r.getBody();
		for (int i = 0; i < literals.size(); i++) {
			Predicate pred = literals.get(i).getPredicate();
			if (prevdelta.keySet().contains(pred)) {
				HashMap<Predicate, HashSet<GroundAtom>> myMap = new HashMap<Predicate, HashSet<GroundAtom>>();
				myMap.put(pred, prevdelta.get(pred));
				int selectedLiteral = i;
				HashSet<GroundAtom> rel = Instantiate(r, myMap,selectedLiteral,loadFromKB);
				if (rel != null){
					for(GroundAtom matom:rel){
						unionRel.add(matom) ;
					}
				}
			}
		}
		return unionRel;
    }

    /**
     * 得到一个规则的结论集合.
     * @param r.要评估的规则
     * @param prevdelta.用于增量是推理，对于非增量式推理，这个参数为NULL
     * @param selectedLiteral. 表明哪个文字使用上一轮推出的事实
     * @param loadFromKB.是否从知识库加载事实
     * @return NULL或者结论集合
     * @throws SQLException 
     */
    private HashSet<GroundAtom> Instantiate(Rule r,HashMap<Predicate,HashSet<GroundAtom>> prevdelta,int selectedLiteral,boolean loadFromKB) throws SQLException{
    	int i;
		ArrayList<Atom<Term>> literals = r.getBody();
		Atom<Term> hatom = r.getHead();
		ArrayList<Variable> Bindings = new ArrayList<Variable>();
		ArrayList<Tuple> relation = new ArrayList<Tuple>();
		for (i = 0; i < literals.size(); i++) {
			boolean flag = (selectedLiteral==i);
			Atom<Term> atom = literals.get(i);
			relation = SubGoalInstance(r, atom, Bindings, relation, prevdelta,flag,loadFromKB);
			if (relation == null)
				return null;
		}
		boolean[] flags = new boolean[hatom.size()];
		int[] pos = new int[hatom.size()];
		for (i = 0; i < hatom.size(); i++) {
			if (hatom.get(i) instanceof Constant) {
				flags[i] =true;
				pos[i] = i;
			} else {
				int index = Bindings.indexOf(hatom.get(i));
				if (index == -1) {
					throw new IllegalArgumentException(
							"The varaible in the head must occur in the body");
				} else {
				    flags[i] = false;
					pos[i] = index ;
				}
			}
		}
		HashSet<GroundAtom> mRelation = new HashSet<GroundAtom>();
		if (relation.size() > 0) {
			for (Tuple tuple : relation) {
				ArrayList<Constant> terms = new ArrayList<Constant>();
				for (i = 0; i < pos.length; i++) {
					if (flags[i]==true) {
						terms.add((Constant) hatom.get(pos[i]));
					} else {
						terms.add(tuple.get(pos[i]));
					}
				}
				Provenance prov = ProvenanceFactory.getInstance()
						.createProvFromReasoning(r, tuple.getProv());
				GroundAtom gAtom = new GroundAtom(hatom.getPredicate(), terms,
						prov);
				mRelation.add(gAtom);
			}
		}
		return mRelation;
    }
    
    /**
     * 如果 subgoal满足, 那么返回实例化这个subgoal的事实集合.<br>
     * 注意形如p('a','b')这样的参数都是常量的 subgoal，返回的是非空集合，只是其中每个Tuple size为0.
 	 * @param r.包含这个subgoal的规则
 	 * @param atom. 这个subgoal对应的公式
 	 * @param prevBindings.在这个Atom之前规则中其它子句evaluate后得到的变量绑定情况
 	 * @param prevRelation. 在这个Atom之间的那些子句对应的事实集合的join结果，并限定到变量位置。 
 	 * @param prevdelta. 用于增量是推理，对于非增量式推理，这个参数为NULL
 	 * @param flag.表明是否使用上一轮推出的事实
 	 * @param loadFromKB.是否从知识库加载事实
 	 * @return NULL or 实例化这个subgoal的事实集合
     * @throws SQLException 
 	*/
    private ArrayList<Tuple> SubGoalInstance(Rule r,Atom<Term> atom,ArrayList<Variable> prevBindings,ArrayList<Tuple> prevRelation,HashMap<Predicate,HashSet<GroundAtom>> prevdelta,boolean flag,boolean loadFromKB) throws SQLException{
    	boolean firstGoal = false;
		if (prevBindings.size() == 0)
			firstGoal = true;
		int i, j;
		Predicate pred = atom.getPredicate();
		Pattern pattern = atom.getPattern();
		ArrayList<Integer> inputBoundIndices = new ArrayList<Integer>();
		ArrayList<Integer> boundArgs = new ArrayList<Integer>();
		ArrayList<Integer> remainArgs = new ArrayList<Integer>();
		ArrayList<Integer> constTerms = new ArrayList<Integer>();
		for (i = 0; i < prevBindings.size(); i++) {
			Variable mVar = prevBindings.get(i);
			for (j = 0; j < pattern.getVarIndices().size(); j++) {
				Variable mVarThisLiteral = (Variable) pattern.getVarMap().get(
						pattern.getVarIndices().get(j));
				if (mVar.equals(mVarThisLiteral)) {
					boundArgs.add(pattern.getVarIndices().get(j));
					inputBoundIndices.add(i);
				}
			}
		}
		for (i = 0; i < atom.size(); i++) {
			if (!boundArgs.contains(i)) {
				if (atom.get(i) instanceof Variable) {
					remainArgs.add(i);
				} else {
					constTerms.add(i);
				}
			}
		}
		// add the new bound variables
		for (i = 0; i < remainArgs.size(); i++) {
			Variable var = (Variable) pattern.getVarMap()
					.get(remainArgs.get(i));
			prevBindings.add(var);
		}
		// for the first goal and no bound literal
		if (boundArgs.size() == 0) {
			HashSet<Tuple> mRelation = new HashSet<Tuple>();
			
			QueryArg key = this.makeQueryArg(pred, pattern) ;
			HashSet<GroundAtom> queryResult = this.getFacts(pred,key,
					pattern.getEqualTerms(), prevdelta,flag,loadFromKB);
			for (GroundAtom gAtom : queryResult) {
				ArrayList<Constant> instantiations = gAtom.getTerms();
				ArrayList<GroundAtom> mlist = new ArrayList<GroundAtom>();
				mlist.add(gAtom);
				mRelation.add(new Tuple(instantiations, mlist));
			}
			// the goal unsatisfiable
			if (mRelation.size() == 0){
				return null;
			}
			// project to the variable
			// the first goal or the goal contains only constant
			// 如果当前subgoal参数都是常量，那么它将到时tuple.size==0但是集合并不为空。
			if (firstGoal) {
				ArrayList<Tuple> concatTuple = new ArrayList<Tuple>();
				for (Tuple rightTuple : mRelation) {
					Tuple emptyTuple = new Tuple(new ArrayList<Constant>(),
							new ArrayList<GroundAtom>());
					Tuple item = concat(emptyTuple, rightTuple, remainArgs);
					concatTuple.add(item);
				}
				return concatTuple;
			}
			ArrayList<Tuple> prevTupleSet = prevRelation;
			ArrayList<Tuple> concatTuple = new ArrayList<Tuple>();
			for (Tuple leftTuple : prevTupleSet) {
				for (Tuple rightTuple : mRelation) {
					Tuple item = concat(leftTuple, rightTuple, remainArgs);
					concatTuple.add(item);
				}
			}
			return concatTuple;
		} else {
			// for second or later literal with some arguments bound
			if (prevRelation == null || prevRelation.size() == 0) {
				throw new IllegalArgumentException(
						"The relation must be not null");
			}
			ArrayList<String> flags= new ArrayList<String>();
			ArrayList<Integer> src = new ArrayList<Integer>();
			ArrayList<Integer> mPos = new ArrayList<Integer>();
			for (i = 0; i < atom.size(); i++) {
				if (constTerms.contains(i)) {
					flags.add("SELF") ;
					src.add(i);
					mPos.add(i);
				} else if (boundArgs.contains(i)) {
					flags.add("PREVIOUS") ;
					src.add(inputBoundIndices.get(boundArgs.indexOf(i)));
					mPos.add(i);
				}else{
					flags.add("NONE") ;
					src.add(null) ;
				}
			}
			ArrayList<Tuple> outputTuple = new ArrayList<Tuple>();
			for (Tuple mTuple : prevRelation) {
				ArrayList<Constant> mConstTerms = new ArrayList<Constant>();
				for (int k = 0;k<atom.size();k++) {
					if (flags.get(k).equals("SELF")) {
						mConstTerms.add((Constant)atom.get(src.get(k)));
					} else if(flags.get(k).equals("PREVIOUS")){
						mConstTerms.add(mTuple.get(src.get(k)));
					}
				}
				QueryArg key = this.makeQueryArg(pred, mPos, mConstTerms);
				HashSet<GroundAtom> queryResult = this.getFacts(pred,key,
						pattern.getEqualTerms(), prevdelta,flag,loadFromKB);
				for (GroundAtom gAtom : queryResult) {
					ArrayList<Constant> rightTerms = gAtom.getTerms();
					ArrayList<GroundAtom> mlist = new ArrayList<GroundAtom>();
					mlist.add(gAtom);
					Tuple item = concat(mTuple, rightTerms, mlist,remainArgs);
					outputTuple.add(item);
				}
			}
			if (outputTuple.size() == 0){
				return null;
			}
			else{
				return outputTuple;
			}
		}
    }
    
    /**
     * 从结论出发修改证据解释，返回推理用到的所有三元组所在的文档集合
     * @param start
     * @return
     */
    private HashSet<String> removeEdgesfromTrace(HashSet<GroundAtom> start){
    	HashSet<String> srcDocs = new HashSet<String>();
    	HashSet<GroundAtom> visited = new HashSet<GroundAtom>();
    	LinkedList<GroundAtom> list = new LinkedList<GroundAtom>();
    	visited.addAll(start) ;
    	list.addAll(start) ;
    	while(list.size()>0){
    		GroundAtom gatom = list.remove();
    		Predicate pred = gatom.getPredicate();
    		if(!( pred.getResource() instanceof TemporaryRDFResource)&&!(pred.getResource() instanceof SupmagicResource)){
    			ArrayList<GroundAtom> items= this.removeEdgesfromTrace(gatom,srcDocs) ;
    			for(GroundAtom item:items){
        			if(!visited.contains(items)){
        				visited.add(item) ;
        				list.add(item) ;
        			}
    			}
       		}
    	}
    	return srcDocs;
    }
    
    /**
     * 
     * @param fact
     * @param srcDocs. 记录原始底层的文档来源
     * @return
     */
    private ArrayList<GroundAtom> removeEdgesfromTrace(GroundAtom fact,HashSet<String> srcDocs){
    	ArrayList<GroundAtom> result = new ArrayList<GroundAtom>();
    	//对于推理得到的事实，除去以magic predicate作为谓词事实
    	Provenance prov = fact.getProvenance();
    	if(prov instanceof FromReasoning){
    		FromReasoning reasonProv = (FromReasoning) prov;
    		Rule rule = reasonProv.getRule();
    		ArrayList<GroundAtom> factsDepended = reasonProv.getGroundAtoms();
    		ArrayList<Atom<Term>> body = rule.getBody();
    		if(body.get(0).getPredicate().getResource() instanceof TemporaryRDFResource){
    			ArrayList<Atom<Term>> modifiedBody = new ArrayList<Atom<Term>>();
    			for(int i=1;i<body.size();i++){
    				modifiedBody.add(body.get(i));
    			}
    			Rule modifiedRule = new Rule(rule.getHead(),modifiedBody,rule.getProvenance());
    			ArrayList<GroundAtom> modifiedFactsDepended = new ArrayList<GroundAtom>();
    			for(int j=1;j<factsDepended.size() ;j++){
    				modifiedFactsDepended.add(factsDepended.get(j)) ;
    			}
    			FromReasoning modifiedProv = ProvenanceFactory.getInstance().createProvFromReasoning(modifiedRule, modifiedFactsDepended) ;
    			fact.setProvenance(modifiedProv) ;
    			result.addAll(modifiedFactsDepended) ;
    		}else if(body.get(0).getPredicate().getResource() instanceof SupmagicResource){
    			ArrayList<Atom<Term>> modifiedBody = new ArrayList<Atom<Term>>();
    			ArrayList<GroundAtom> modifiedFactsDepended = new ArrayList<GroundAtom>();
    			for(int i=body.size()-1;i>=1;i--){
    				modifiedBody.add(body.get(i));
    			}
    			ArrayList<Atom<Term>> todoList = new ArrayList<Atom<Term>>();
    			todoList.add(body.get(0)) ;
    			while(todoList.size()>0){
    				Atom<Term> mfact = todoList.remove(0) ;
    				for(Rule r:this.rules.getRulesWithPred(mfact.getPredicate())){
    					ArrayList<Atom<Term>> list = r.getBody();
    					if(list.get(0).getPredicate().getResource() instanceof SupmagicResource){
    						todoList.add(list.get(0)) ;
    						for(int i=list.size()-1;i>=1;i--){
    		    				modifiedBody.add(list.get(i));
    		    			}
    					}else if(list.get(0).getPredicate().getResource() instanceof TemporaryRDFResource){
    						for(int i=list.size()-1;i>=1;i--){
    		    				modifiedBody.add(list.get(i));
    		    			}
    					}else{
    						for(int i=list.size()-1;i>=0;i--){
    		    				modifiedBody.add(list.get(i));
    		    			}
    					}
    				}
    			}
    			Collections.reverse(modifiedBody);
    			Rule modifiedRule = new Rule(rule.getHead(),modifiedBody,rule.getProvenance());
    			for(int j=factsDepended.size()-1;j>=1 ;j--){
    				modifiedFactsDepended.add(factsDepended.get(j)) ;
    			}
    			ArrayList<GroundAtom> todo = new ArrayList<GroundAtom>();
    			todo.add(factsDepended.get(0)) ;
    			while(todo.size()>0){
    				GroundAtom mfact = todo.remove(0) ;
    		    	Provenance mprov = mfact.getProvenance();
    		    	FromReasoning mreasonProv = (FromReasoning) mprov;
    	    		ArrayList<GroundAtom> mfactsDepended = mreasonProv.getGroundAtoms();
					if(mfactsDepended.get(0).getPredicate().getResource() instanceof SupmagicResource){
						todo.add(mfactsDepended.get(0)) ;
						for(int i=mfactsDepended.size()-1;i>=1;i--){
							modifiedFactsDepended.add(mfactsDepended.get(i));
		    			}
					}else if(mfactsDepended.get(0).getPredicate().getResource() instanceof TemporaryRDFResource){
						for(int i=mfactsDepended.size()-1;i>=1;i--){
							modifiedFactsDepended.add(mfactsDepended.get(i));
		    			}
					}else{
						for(int i=mfactsDepended.size()-1;i>=0;i--){
							modifiedFactsDepended.add(mfactsDepended.get(i));
		    			}
					}
    			}
    			Collections.reverse(modifiedFactsDepended);
    			FromReasoning modifiedProv = ProvenanceFactory.getInstance().createProvFromReasoning(modifiedRule, modifiedFactsDepended) ;
    			fact.setProvenance(modifiedProv) ;
    			result.addAll(modifiedFactsDepended) ;
    		}else{
    			result.addAll(factsDepended);
    		}
    	}else if(prov instanceof FromRDFDocument){
    		FromRDFDocument docProv = (FromRDFDocument)prov;
    		srcDocs.add(docProv.getRDFDocument().getURI().getURI());
    	}
    	return result;
    }
    
    private Tuple concat (Tuple left ,Tuple right, ArrayList<Integer> remainArgs){
    	int i;
    	 ArrayList<GroundAtom> provLeft= left.getProv();
   	    ArrayList<GroundAtom> provRight = right.getProv();
   	    ArrayList<GroundAtom> mList = new ArrayList<GroundAtom>(provLeft.size()+provRight.size());
		int argNumber = left.size() + remainArgs.size();
		ArrayList<Constant> terms = new ArrayList<Constant>(argNumber);
		terms.addAll(left.getTerms()) ;
		for (i=left.size(); i < argNumber; i++) {
			terms.add(right.get(remainArgs.get(i - left.size())));
		}
		mList.addAll(provLeft) ;
		mList.addAll(provRight) ;
		Tuple tuple = new Tuple(terms,mList);
		return tuple;
    }
    
    private Tuple concat(Tuple left,ArrayList<Constant> rightTerms,ArrayList<GroundAtom> provRight,ArrayList<Integer> remainArgs){
    	int i;
   	    ArrayList<GroundAtom> provLeft= left.getProv();
  	    ArrayList<GroundAtom> mList = new ArrayList<GroundAtom>(provLeft.size()+provRight.size());
		int argNumber = left.size() + remainArgs.size();
		ArrayList<Constant> terms = new ArrayList<Constant>(argNumber);
		terms.addAll(left.getTerms()) ;
		for (i=left.size(); i < argNumber; i++) {
			terms.add(rightTerms.get(remainArgs.get(i - left.size())));
		}
		mList.addAll(provLeft) ;
		mList.addAll(provRight) ;
		Tuple tuple = new Tuple(terms,mList);
		return tuple;
    }
	
    /**
     * 对记录哪些谓词新的外延的结构进行更新
     * @param delta. 记录哪些谓词新的外延的结构
     * @param pred. 
     * @param relation
     * @return
     */
    private void updateDelta(HashMap<Predicate,HashSet<GroundAtom>> delta,Predicate pred, HashSet<GroundAtom> relation){
    	if(!delta.containsKey(pred)){
   		  delta.put(pred, relation) ;
   	  }else{
   		  HashSet<GroundAtom> _relation = delta.get(pred) ;
   		  for(GroundAtom matom :relation){
   			  _relation.add(matom) ;
   		  }
   	  }
    }
	
	/**
	 * 从当前要考虑的集合中删除已经出现在内存working memory中的事实
	 * @param  pred.
	 * @param relation.
	 * @return
	 */
    private HashSet<GroundAtom> removeDeducedTuples(Predicate pred,HashSet<GroundAtom> relation){
		HashSet<GroundAtom> mFacts = this.facts.getRelation(pred);
		if (mFacts.size() == 0 || relation.size() == 0) {
			return relation;
		}
		HashSet<GroundAtom> mRelation = new HashSet<GroundAtom>();
		for (GroundAtom fact : relation) {
			if (!mFacts.contains(fact)) {
				mRelation.add(fact);
			}
		}
		return mRelation;
    }
    
    private QueryArg makeQueryArg(Predicate pred,Pattern pattern){
           ArrayList<Integer> constArray = pattern.getConstIndices();
           ArrayList<Constant> argArray =  pattern.getConstTerms();
           return makeQueryArg(pred,constArray,argArray) ;
    }
    
    private QueryArg makeQueryArg(Predicate pred,ArrayList<Integer> constArray, ArrayList<Constant> argArray){
    	QueryArg key = null;
          if(constArray.size()==2){
          	 key = new BothArg(argArray.get(0),argArray.get(1)) ;
          }else if(constArray.size()==1){
          	if(constArray.get(0).equals(new Integer(0))){
          		key = new FirstArg(argArray.get(0));
          	}else{
          		key = new SecondArg(argArray.get(0));
          	}
          }
          return key;
    }
    
    /**
     * check whether the reasoning result is larger than TERMINATE_NUM 
     * @param query
     * @param loadFromKB
     * @return
     */
    public boolean isTerminate(Atom<Term> query,boolean loadFromKB){
    	boolean flag = false;
    	Predicate pred = query.getPredicate();
		Pattern pattern = query.getPattern();
		QueryArg  key = this.makeQueryArg(pred, pattern) ;
		try {
			HashSet<GroundAtom> queryResult = this.getFacts(pred,key, pattern
					.getEqualTerms(), null,false,loadFromKB);
			if(queryResult.size()>KnowledgeBase.TERMINATE_NUM){
				flag = true;
			}
				
		} catch (SQLException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return flag;
    }
    
    public WorkingMemory getWorkingMemory() {
		return this.facts;
	}
    
	public ProductionMemory getProductionMemory() {
		return rules;
	}
	
    public void Reset(){
    	this.rules.reset();
    	this.facts.Reset();
    }
    
    public String toString(){
      	 StringBuffer sb = new StringBuffer();
      	 sb.append("Rules:\n");
      	 sb.append(rules) ;
      	 sb.append("\n");
      	 sb.append("Facts:\n") ;
      	 sb.append(facts) ;
      	 return sb.toString();
    }
    
    private class Tuple{
    	private int hash;
    	ArrayList<Constant> terms = null;
    	ArrayList<GroundAtom> prov = null;
    	
    	Tuple(ArrayList<Constant> terms,ArrayList<GroundAtom> prov){
    		this.terms = terms;
    		this.prov = prov;
    	}
    	
    	public ArrayList<Constant> getTerms(){
    		return terms;
    	}
    	
    	public ArrayList<GroundAtom> getProv(){
    		return this.prov;
    	}
    	
    	public int size(){
    		return terms.size();
    	}
    	
    	public Constant get(int i){
    		return terms.get(i) ;
    	}
		@Override
		public int hashCode() {
	        int h = this.hash;
	        if(h==0){
	        	int prime = 853;
	        	int hashcode = 1;
	        	for(int i=0;i<this.terms.size();i++){
	        		hashcode=prime*hashcode+this.terms.get(i).hashCode() ;
	        	}
	        	h = hashcode;
	        	this.hash = h;
	        }
			return h;
		}
		@Override
		public boolean equals(Object obj) {
            if(obj instanceof Tuple){
            	Tuple mtuple = (Tuple)obj;
            	if(this.terms.equals(mtuple.terms))
            		return true;
            }
			return false;
		}
		
		public String toString(){
			return this.terms.toString();
		}
    }
}
